package com.my.collection.tree.v1;

import com.my.collection.graph.v1.Queue;
import com.my.collection.graph.v1.Stack;

import java.util.*;

/**
 * Created by Scarlett on 2018/10/12 0012.
 */
public class Tree<E> {

    private Node<E> root;


    public Tree(E[] elements) {
        if (elements == null || elements.length < 1) {
            throw new IllegalArgumentException();
        }

        Node<E>[] nodes = new Node[elements.length];
        for (int i = 0; i < elements.length; i++) {
            if (elements[i] == null) {
                nodes[i] = null;
            } else {
                nodes[i] = new Node<>(elements[i], null, null, null);
            }
        }

        for (int i = 0; i < nodes.length / 2; i++) {
            Node<E> node = nodes[i];
            if (2 * i + 1 < elements.length) {
                node.left = nodes[2 * i + 1];
                if (node.left != null) {
                    node.left.parent = node;
                }
            }
            if (2 * i + 2 < elements.length) {
                node.right = nodes[2 * i + 2];
                if (node.right != null) {
                    node.right.parent = node;
                }
            }
        }

        this.root = nodes[0];
    }

    /**
     * 层序遍历
     * <p>
     * 伪代码
     * 构造一个空的队列和遍历的列表，将根结点入队
     * 循环判断队列是否为空，不为空进行循环
     * 出队操作得到结点，放入遍历列表
     * 如果出队结点的左子节点不为空，入队
     * 如果出队结点的右子节点不为空，入队
     * 返回遍历列表
     *
     * @return
     */
    public List<E> levelOrder() {
        Queue<Node<E>> queue = new Queue<>();
        List<E> visited = new ArrayList<>();

        if (this.root == null) {
            return visited;
        }

        queue.enq(this.root);
        while (!queue.isEmpty()) {
            Node<E> deq = queue.deq();
            visited.add(deq.data);

            if (deq.left != null) {
                queue.enq(deq.left);
            }

            if (deq.right != null) {
                queue.enq(deq.right);
            }
        }

        return visited;
    }

    /**
     * 前序遍历 根-》左-》右
     * <p>
     * 伪代码
     * 构造一个空的栈和遍历的列表，将根结点入栈
     * 循环判断栈是否为空，不为空进行循环
     * 出栈操作得到结点，放入遍历列表
     * 如果出栈结点的右子节点不为空，入栈
     * 如果出栈结点的左子节点不为空，入栈
     * 返回遍历列表
     *
     * @return
     */
    public List<E> preOrder() {
        Stack<Node<E>> stack = new Stack<>();
        List<E> visited = new ArrayList<>();

        if (this.root == null) {
            return visited;
        }

        stack.push(this.root);
        while (!stack.isEmpty()) {
            Node<E> pop = stack.pop();
            visited.add(pop.data);

            if (pop.right != null) {
                stack.push(pop.right);
            }

            if (pop.left != null) {
                stack.push(pop.left);
            }
        }
        return visited;
    }


    /**
     * 前序遍历递归版本
     *
     * @param visited
     * @param node
     */
    private void preOrder(List<E> visited, Node<E> node) {
        if (node.left != null) {
            preOrder(visited, node.left);
        }

        visited.add(node.data);

        if (node.right != null) {
            preOrder(visited, node.right);
        }
    }

    /**
     * 中序遍历 左-》根-》右
     * <p>
     * 伪代码：
     * 构造一个空的栈和遍历列表
     * 将根结点入栈
     * 循环遍历结点的左子结点，如果不为空，入栈
     * 循环判断栈是否为空，不为空进入循环
     * 出栈元素，添加进遍历列表
     * 如果出栈元素的右子节点不为空，进行入栈操作
     * 循环遍历结点的左子结点，如果不为空，入栈
     * 返回遍历列表
     *
     * @return
     */
    public List<E> inOrder() {
        Stack<Node<E>> stack = new Stack<>();
        List<E> visited = new ArrayList<>();
        if (this.root == null) {
            return visited;
        }

        Node<E> tmp = this.root;
        stack.push(tmp);
        while ((tmp = tmp.left) != null) {
            stack.push(tmp);
        }

        while (!stack.isEmpty()) {
            Node<E> pop = stack.pop();
            visited.add(pop.data);

            if (pop.right != null) {
                stack.push(pop.right);
                Node<E> t = pop.right;
                while ((t = t.left) != null) {
                    stack.push(t);
                }
            }
        }

        return visited;
    }

    /**
     * 中序遍历递归版本
     *
     * @param visited
     * @param node
     */
    private void inOrder(List<E> visited, Node<E> node) {
        if (node.left != null) {
            inOrder(visited, node.left);
        }

        visited.add(node.data);

        if (node.right != null) {
            inOrder(visited, node.right);
        }
    }

    /**
     * 后序遍历 左-》右-》根
     * <p>
     * 伪代码：
     * 按照前序遍历的代码进行根右左的遍历
     * 再将遍历的列表进行倒置，就得到后序遍历的结果，左右根
     *
     * @return
     */
    public List<E> postOrder() {
        Stack<Node<E>> stack = new Stack<>();
        List<E> visited = new ArrayList<>();

        if (this.root == null) {
            return visited;
        }

        stack.push(this.root);
        while (!stack.isEmpty()) {
            Node<E> pop = stack.pop();
            visited.add(pop.data);

            if (pop.left != null) {
                stack.push(pop.left);
            }

            if (pop.right != null) {
                stack.push(pop.right);
            }
        }

        Collections.reverse(visited);
        return visited;
    }

    /**
     * 后序遍历递归版本
     *
     * @param visited
     * @param node
     */
    private void postOrder(List<E> visited, Node<E> node) {
        if (node.left != null) {
            postOrder(visited, node.left);
        }

        if (node.right != null) {
            postOrder(visited, node.right);
        }

        visited.add(node.data);
    }


    /**
     * 找到二叉树的最长路径
     * 伪代码：
     * 构造一个空的列表
     * 层序遍历二叉树，获得最后一个叶子节点
     * 从叶子节点向上依次找到其父节点，直到根节点，依次添加节点至列表中
     * 对列表执行倒排动作，获取最长路径
     * <p>
     * 注：获取的最长路径可能只是某一条
     *
     * @return
     */
    public List<E> theLongestPath() {
        List<E> path = new ArrayList<>();
        List<Node<E>> elements = levelOrder1();
        if (elements.isEmpty()) {
            return path;
        }

        Node<E> lastNode = elements.get(elements.size() - 1);
        while (lastNode != null) {
            path.add(lastNode.data);
            lastNode = lastNode.parent;
        }

        Collections.reverse(path);
        return path;
    }

    /**
     * 找寻所有二叉树的最长路径
     *
     * @return
     */
    public List<List<E>> theLongestPaths() {
        List<Node<E>> nodes = new ArrayList<>();
        nodes.add(this.root);

        while (!nodes.isEmpty()) {
            List<Node<E>> sameLevelNodes = new ArrayList<>();
            for (Node<E> node : nodes) {
                if (node.left != null) {
                    sameLevelNodes.add(node.left);
                }
                if (node.right != null) {
                    sameLevelNodes.add(node.right);
                }
            }

            if (sameLevelNodes.isEmpty()) {
                break;
            }

            nodes.clear();
            nodes.addAll(sameLevelNodes);
        }

        List<List<E>> paths = new ArrayList<>();
        for (Node<E> node : nodes) {
            List<E> path = new ArrayList<>();
            while (node != null) {
                path.add(node.data);
                node = node.parent;
            }
            Collections.reverse(path);
            paths.add(path);
        }

        return paths;
    }

    private List<Node<E>> levelOrder1() {
        Queue<Node<E>> queue = new Queue<>();
        List<Node<E>> visited = new ArrayList<>();

        if (this.root == null) {
            return visited;
        }

        queue.enq(this.root);
        while (!queue.isEmpty()) {
            Node<E> deq = queue.deq();
            visited.add(deq);

            if (deq.left != null) {
                queue.enq(deq.left);
            }

            if (deq.right != null) {
                queue.enq(deq.right);
            }
        }

        return visited;
    }

    /**
     * 获得二叉树的最大高度
     *
     * @return
     */
    public int maxHeight() {
        return height(this.root);
    }

    private int height(Node<E> node) {
        if (node == null) {
            return 0;
        }

        int left = height(node.left);
        int right = height(node.right);
        return Math.max(left, right) + 1;
    }

    /**
     * 二叉树的最短路径
     * 伪代码：
     * 构造一个空的列表
     * 层序遍历二叉树，找到第一个叶子节点
     * 从该叶子节点向上遍历，将遍历节点加入列表，直到遍历至根结点
     * 对列表倒转即得到最短路径之一
     * <p>
     * 注：该最短路径可能并不是唯一的最短路径
     *
     * @return
     */
    public List<E> theShortestPath() {
        List<E> path = new ArrayList<>();
        Node<E> firstLeaf = null;

        Queue<Node<E>> queue = new Queue<>();
        queue.enq(this.root);
        while (!queue.isEmpty()) {
            Node<E> deq = queue.deq();
            if (deq.left == null && deq.right == null) {
                firstLeaf = deq;
                break;
            }

            if (deq.left != null) {
                queue.enq(deq.left);
            }

            if (deq.right != null) {
                queue.enq(deq.right);
            }
        }

        while (firstLeaf != null) {
            path.add(firstLeaf.data);
            firstLeaf = firstLeaf.parent;
        }

        Collections.reverse(path);
        return path;
    }

    /**
     * 二叉树的所有最短路径
     * 伪代码：
     * 构造一个空的二维列表
     * 层序遍历二叉树，找到第一个叶子节点及其同层的所有其它叶子节点
     * 针对所有叶子节点依次执行以下操作：
     * 从该叶子节点向上遍历，将遍历节点加入列表，直到遍历至根结点
     * 对列表倒转即得到最短路径，添加进列表中
     * 返回二维列表
     *
     * @return
     */
    public List<List<E>> theShortestPaths() {
        List<Node<E>> nodes = new ArrayList<>();
        nodes.add(this.root);

        List<Node<E>> leafNodes = new ArrayList<>();
        while (!nodes.isEmpty()) {
            List<Node<E>> sameLevelNodes = new ArrayList<>();
            for (Node<E> node : nodes) {
                if (node.left == null && node.right == null) {
                    leafNodes.add(node);
                } else {
                    if (node.left != null) {
                        sameLevelNodes.add(node.left);
                    }

                    if (node.right != null) {
                        sameLevelNodes.add(node.right);
                    }
                }
            }

            if (leafNodes.isEmpty()) {
                nodes.clear();
                nodes.addAll(sameLevelNodes);
            } else {
                break;
            }
        }

        List<List<E>> paths = new ArrayList<>();
        for (Node<E> leafNode : leafNodes) {
            List<E> path = new ArrayList<>();
            while (leafNode != null) {
                path.add(leafNode.data);
                leafNode = leafNode.parent;
            }
            Collections.reverse(path);
            paths.add(path);
        }

        return paths;
    }

    /**
     * 找寻二叉树的所有叶子节点
     *
     * @return
     */
    public List<E> leafNodes() {
        List<E> nodes = new ArrayList<>();
        leafNodes(this.root, nodes);
        return nodes;
    }

    private void leafNodes(Node<E> node, List<E> nodes) {
        if (node == null) {
            return;
        }

        if (node.left == null && node.right == null) {
            nodes.add(node.data);
        } else {
            leafNodes(node.left, nodes);
            leafNodes(node.right, nodes);
        }
    }

    /**
     * 找寻所有叶子节点，同时返回每个叶子节点所有的层数，根节点算1层
     *
     * @return
     */
    public Map<E, Integer> allLeafNodes() {
        Map<E, Integer> nodes = new HashMap<>();
        leafNodes(this.root, nodes, 1);
        return nodes;
    }

    private void leafNodes(Node<E> node, Map<E, Integer> nodes, int level) {
        if (node == null) {
            return;
        }

        if (node.left == null && node.right == null) {
            nodes.put(node.data, level);
        } else {
            leafNodes(node.left, nodes, level + 1);
            leafNodes(node.right, nodes, level + 1);
        }
    }

    /**
     * 判断二叉树是否是平衡的
     * 任意结点的左右子树的高度差不超过1
     *
     * @return
     */
    public boolean isBalance() {
        return isBalance(this.root);
    }

    private boolean isBalance(Node<E> node) {
        return node == null || height(node.left) - height(node.right) <= 1 && isBalance(node.left) && isBalance(node.right);
    }

    private static class Node<E> {
        E data;
        Node<E> parent;
        Node<E> left;
        Node<E> right;

        public Node(E data, Node<E> parent, Node<E> left, Node<E> right) {
            this.data = data;
            this.parent = parent;
            this.left = left;
            this.right = right;
        }
    }

}
